package com.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class SubtreeofAnotherTree0301_572 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> que = new LinkedList<>();
        if(root != null) que.offer(root);
        boolean res = false;
        while (!que.isEmpty()){
            int len = que.size();

            while (len > 0){
                TreeNode node = que.poll();
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
                res = compareTree(node,subRoot);
                if(res) return res;

                len--;
            }
        }
        return res;
    }

    private boolean compareTree(TreeNode node, TreeNode subRoot) {
        if(node == null && subRoot == null) return true;
        else if(node != null && subRoot == null) return false;
        else if(node == null && subRoot != null) return false;
        else if(node.val != subRoot.val) return false;

        boolean left = compareTree(node.left,subRoot.left);
        boolean right = compareTree(node.right,subRoot.right);

        return left && right;
    }
}
